
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* newhead,ListNode* head)
    {
        ListNode* curA,*curB;
        curA = newhead;
        curB =head;
        int len1 =1;
        int len2 =1;

        while(curA->next)
        {
            curA = curA->next;
            ++len1;
        }

        while(curB->next)
        {
            curB = curB->next;
            ++len2;
        }

        if(curA != curB)
            return NULL;

        ListNode* shortList = head;
        ListNode* longList = newhead;
        if(len2 > len1)
        {
            shortList = newhead;
            longList = head;
        }
        int gap = abs(len1-len2);
        while(gap--)
        {
            longList = longList->next;
        }
        while(longList != shortList)
        {
            longList = longList->next;
            shortList = shortList->next;
        }

        return longList; 
    }

    ListNode *detectCycle(ListNode *head) {
        ListNode* slow,*fast;
        slow = fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            
            if(slow == fast)
            {
                ListNode* meet = slow;
                ListNode* newhead= meet->next;
                slow->next = NULL;

                return getIntersectionNode(newhead,head);
            }
        }

    return NULL;
    }
};



class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow,*fast;
        slow = fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow)
            {
                ListNode* meet = slow;
                while(head != meet)
                {
                    head = head->next;
                    meet = meet->next;
                }
                return meet;
            }
        }
        
        return NULL;
    }
};
